#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
struct ListNode {
	int val;
	struct ListNode* next;
};

struct ListNode* removeElements(struct ListNode* head, int val) {
	struct ListNode* tail = head;
	struct ListNode* tailprev = NULL;
	while (tail)
	{
		if (tail->val == val) {
			struct ListNode* next = tail->next;
			if (tailprev==NULL)
			{
				head = next;
			}
			else 
			{
				tailprev->next = tail->next;
			}
			free(tail);
			tail = next;
		}
		else
		{
			tailprev = tail;
			tail = tail->next;
		}
	}
	return head;
}

struct ListNode* reverseList(struct ListNode* head) {
	struct ListNode* tail = head; 
	struct ListNode* tailprev = NULL;
	while (tail)
	{
		struct ListNode* next = tail->next;
		tail->next = tailprev;
		tailprev = tail;
		tail =next;
	}
	return tailprev;
}

struct ListNode* middleNode(struct ListNode* head) {
	struct ListNode* tail = head; 
	struct ListNode* tailprev = head;
	int count = 0; 
	int num = 0;
	while (tail)
	{
		tail = tail->next;
		count++;
	}
	num = count / 2 ;
	
	while (num--)
	{
		tailprev = tailprev->next;
	}
	return tailprev;
}

int kthToLast(struct ListNode* head, int k) {
	struct ListNode* tail = head;
	struct ListNode* tailprev = head;
	int count = 0;
	while (tail)
	{
		tail = tail->next;
		count++;
	}
	int num = count - k;
	while (num--)
	{
		tailprev = tailprev->next;
	}
	return tailprev->val;
}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
	struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
	dummyHead->val = -1;
	dummyHead->next = NULL;
	struct ListNode* tail = dummyHead;
	while (list1 != NULL || list2 != NULL) {
		if (list1 == NULL) {
			tail->next = list2;
			break;
		}
		if (list2 == NULL) {
			tail->next = list1;
			break;
		}
		if (list1->val > list2->val) {
			tail->next = list2;
			tail = tail->next;
			list2 = list2->next;
		}
		else {
			tail->next = list1;
			tail = tail->next;
			list1 = list1->next;
		}
	}
	return dummyHead->next;
}

struct ListNode* mergeTwoLists_1(struct ListNode* list1, struct ListNode* list2) {
	if (list1 == NULL) {
		return list2;
	}
	if (list2 == NULL) {
		return list1;
	}
	struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
	dummyHead->val = -1;
	dummyHead->next = NULL;
	struct ListNode* tail = dummyHead;
	while (list1 && list2) {
		if (list1->val > list2->val) {
			struct ListNode* next = list2->next;
			tail->next = list2;
			tail = tail->next;
			list2 = next;
		}
		else {
			struct ListNode* next = list1->next;
			tail->next = list1;
			tail = tail->next;
		}
	}
	return dummyHead->next;
}

struct ListNode* reverseList_1(struct ListNode* head) {
	struct ListNode* cur = head;
	struct ListNode* newhead = NULL;
	while (cur) {
		struct ListNode* next = cur->next;
		cur->next = newhead;
		newhead = cur;
		cur = next;
	}
	return newhead;
}